package classics.Tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * ex199 二叉树的右视图
 * 层序遍历
 */
public class Ex199 {

  public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }


    public List<Integer> rightSideView(TreeNode root) {
        if(root==null){
            return new ArrayList<>();
        }
        Deque<TreeNode> qu = new LinkedList<>();
        List<List<Integer>> list = new ArrayList<>();
        qu.add(root);
        while(!qu.isEmpty()){
            List<Integer> temp = new ArrayList();
            int size = qu.size();
            while(size-->0){
                TreeNode node = qu.pollFirst();
                temp.add(node.val);
                if(node.left!=null){
                    qu.addLast(node.left);
                }
                if(node.right!=null){
                    qu.addLast(node.right);
                }
            }
            list.add(temp);
        }
        List<Integer> res = new ArrayList<>();
        for(List<Integer> a: list){
            res.add(a.get(a.size()-1));
        }
        return res;
    }
}
